package ch09_03;

import java.util.Arrays;
public class Solution {
    public static int magicIndex1(int[] A) {
	int low = 0;
	int high = A.length - 1;
	int mid = -1;
	while (low < high) {
	    mid = low + (high - low) / 2;
	    if (A[mid] == mid) {
		return mid;
	    } else if (A[mid] < mid) {
		low = mid + 1;
	    } else {
		high = mid;
	    }
	}
	return -1;
    }

    public static int magicIndex2(int[] A) {
	int low = 0;
	int high = A.length - 1;
	return find(A, low, high);
    }

    private static int find(int[] A, int low, int high) {
	if (low > high)
	    return -1;
	int mid = low + (high - low) / 2;
	if (A[mid] == mid) {
	    return mid;
	}
	if (low == high) {
		return -1;
	}
	if (A[mid] > high) {
	    return find(A, low, mid);
	}
	if (A[mid] < low) {
	    return find(A, mid + 1, high);
	}
	int left = find(A, low, mid);
	if (left == -1)
	    return find(A, mid + 1, high);
	else
	    return left;
    }

    public static void main(String... args) {
	int N = 10;
	int[] array = new int[N];
	for (int i = -2; i <= 12; i++) {
	Arrays.fill(array, 
			i
			);
	int result = magicIndex2(array);
	System.out.println("i is " + i + ", result is " + result);
	}
    }
}